A finite state machine (FSM) (also referred to as a finite-state automaton, automaton, or simply a state machine) is a representation of states, transitions between states and actions. A finite state machine can be used to design digital logic, computer programs, or images for a parallel machine. A finite state machine is a model of behavior composed of a finite number of states, transitions between those states, and outputs. A finite state machine can be represented as a graph where vertices of the graph correspond to states of the FSM and edges of the graph correspond to transitions between the states which occur due to one or more inputs to the finite state machine. Finite state machines can also have probabilistic transitions, fuzzy states, or other oddities. A finite state machine can function as a finite internal memory having an input feature and an optional output feature. Finite state machines having an output can be referred to as finite state transducers.
Applications of finite state machines include electronic design automation, communication protocol design, biology and artificial intelligence research, and linguistics to describe the grammars of natural languages.